package com.dylon.sort;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] a = new int[]{2,5,3,1,4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }


    public static void sort(int[] a) {
        int d = a.length; // 数组长度
        int tmp; // 插入排序 临时变量
        int group = d;  // 默认分组数
        for (; group>=1; group/=2) { // 分组开始 分成 group
            for (int i = group; i < a.length; i++) { // 依次处理各组“插排” ，到哪个元素就看这个元素在的哪个组即可
                tmp = a[i];
                for (int j = i - group; j >= 0; j -= group) {
                    if (a[j] > tmp) {
                        a[j + group] = a[j];
                        a[j] = tmp;
                    } else {
                        break;
                    }
                }
            }
        }
    }

    /*
    希尔排序 是在插入排序之前做分组处理，减少数据移动位次
        排序前先将数据分成 group = length/2 组
            在依次分成  group = group/2 组 直到 group=1 结束
        每分一次组，进行组内插入排序



     */

}
